স্প্যানিং ট্রি (Spanning Tree)
স্প্যানিং ট্রি হল একটি সংযুক্ত গ্রাফের এমন একটি সাব-গ্রাফ যা গ্রাফের সকল নোডকে সংযুক্ত করে কিন্তু কোন চক্র (Cycle) তৈরি করে না। এটি মূল গ্রাফের সব নোড অন্তর্ভুক্ত করে এবং শুধুমাত্র \( n - 1 \) টি এজ থাকে, যেখানে \( n \) হল নোডের সংখ্যা। স্প্যানিং ট্রিতে মূল গ্রাফের তুলনায় কম এজ থাকে এবং এটি এমনভাবে গঠিত হয় যে প্রতিটি নোড অন্য নোডের সাথে সংযুক্ত থাকে।
বৈশিষ্ট্যসমূহ
- প্রতিটি সংযুক্ত গ্রাফের জন্য একাধিক স্প্যানিং ট্রি থাকতে পারে।
- স্প্যানিং ট্রিতে চক্র থাকে না।
- যদি গ্রাফে \( n \) টি নোড থাকে, তবে স্প্যানিং ট্রিতে সর্বদা \( n - 1 \) টি এজ থাকবে।
মিনিমাম স্প্যানিং ট্রি (Minimum Spanning Tree)
মিনিমাম স্প্যানিং ট্রি (MST) হল একটি বিশেষ ধরনের স্প্যানিং ট্রি যেখানে স্প্যানিং ট্রির এজগুলির মোট ওজন সর্বনিম্ন হয়। ওজনযুক্ত গ্রাফে বিভিন্ন এজের ওজন থাকতে পারে, এবং মিনিমাম স্প্যানিং ট্রি সেই ট্রি যা নোডগুলোকে সংযুক্ত করতে সর্বনিম্ন ওজনের এজ ব্যবহার করে।
বৈশিষ্ট্যসমূহ
- মিনিমাম স্প্যানিং ট্রি শুধুমাত্র ওজনযুক্ত গ্রাফের জন্য প্রযোজ্য।
- এজের মোট ওজন সর্বনিম্ন।
- একটি গ্রাফের একাধিক মিনিমাম স্প্যানিং ট্রি থাকতে পারে যদি একাধিক এজের ওজন সমান হয়।
উদাহরণ
একটি শহরের রাস্তাগুলিকে এমনভাবে সংযুক্ত করতে হবে যাতে রাস্তাগুলির নির্মাণ খরচ সর্বনিম্ন হয়, সেখানে মিনিমাম স্প্যানিং ট্রি ব্যবহার করা হয়।
মিনিমাম স্প্যানিং ট্রি খোঁজার অ্যালগরিদম
প্রিমস অ্যালগরিদম (Prim's Algorithm): এই অ্যালগরিদমটি একটি নোড থেকে শুরু করে প্রতিবারে সবচেয়ে কম ওজনের এজ যোগ করে গ্রাফের সকল নোডকে সংযুক্ত করে।
ক্রাসকালস অ্যালগরিদম (Kruskal's Algorithm): এই অ্যালগরিদমটি গ্রাফের এজগুলিকে ওজনের ক্রমানুসারে সাজায় এবং চক্র তৈরি না করে সবচেয়ে কম ওজনের এজগুলিকে যুক্ত করে MST গঠন করে।
বাস্তব জীবনে প্রয়োগ (Applications)
- নেটওয়ার্ক ডিজাইন: কম্পিউটার নেটওয়ার্ক, টেলিকমিউনিকেশন নেটওয়ার্ক বা রাস্তার নেটওয়ার্কের ন্যূনতম খরচে সংযোগের জন্য MST ব্যবহার করা হয়।
- ক্লাস্টারিং অ্যালগরিদম: ডেটা ক্লাস্টারিংয়ে মিনিমাম স্প্যানিং ট্রি ব্যবহার করে ক্লাস্টার তৈরি করা যায়।
সারসংক্ষেপ (Summary)
স্প্যানিং ট্রি হল একটি সংযুক্ত গ্রাফের চক্রবিহীন সাব-গ্রাফ যা নোডগুলিকে সংযুক্ত করে। মিনিমাম স্প্যানিং ট্রি হল এমন একটি স্প্যানিং ট্রি যার মোট এজের ওজন সর্বনিম্ন। এটি নেটওয়ার্ক ডিজাইন, রাস্তা নির্মাণ এবং ক্লাস্টারিংয়ের মতো বিভিন্ন ক্ষেত্রে গুরুত্বপূর্ণ। প্রিমস এবং ক্রাসকালস অ্যালগরিদম MST খুঁজে বের করতে ব্যবহৃত হয়।
Read more
